Packetized data networks are relatively well known. Such networks include Ethernet networks, Internet Protocol (IP) networks and asynchronous transfer mode (ATM) networks. The data packets carried by these networks typically have some sort of informational header file or header data to which a data payload is attached or appended. The header is formatted to have embedded within it various information that is used to route the associated payload to an appropriate destination. By way of example, FIG. 1 shows an exemplary depiction of an ATM data packet.
An ATM data packet (100) consists of forty-eight (48) informational payload bytes (102) (identified in FIG. 1 as byte octets numbered from 6–53) preceded by a five (5) byte header block (104) to form a fifty-three byte ATM packet (100). The informational payload bytes (102) represent information from some sort of data source, which might include voice information as part of a telephone call, video programming information or raw data exchanged between two computers such as a word processing file for example. The header block (104) includes addressing information that is read by and used by ATM switching systems (not shown) which route the ATM packet (100) through an ATM switching network. Some of the information in the header block 104 enables a switch to determine the next ATM switch to which the packet is to be routed.
FIG. 2 shows exemplary connections to a known prior art ATM switching system 200 as it might be configured in an ATM network. Such a system is typically configured to receive streams of ATM packets from multiple ATM switching systems at the switch input ports 202, 204, 206. When the packets comprising the incoming streams are received, they are routed to a switching fabric 210 from which the packets emerge at one or more ATM packet output ports 212, 214, 216 coupled to different physical transmission paths leading to different ATM switches in the network. Each input port 202, 204, 206 may receive ATM cells that need to pass through any given output port 212, 214, 216. Likewise, each output port 212, 214, 216 may receive ATM cells from any given input port 202, 204, 206.
Depending on the design of the switching fabric there may be points, referred to here as contention points, where more packets may arrive then may leave in a given time interval. At these points buffers are used to store the data until it can be forwarded. If too much data must be stored then one of these buffers may overflow and the data is lost. For example data packets can be lost in the switching system 200 if too many data packets destined for the same output port 212, 214, 216 are sent into the switch fabric 210 too quickly from the input ports 202, 204, 206. Fixed length internal data packets are forwarded from contention points at a fixed rate. If multiple internal data packets converge on any point in the switch fabric faster than they can be forwarded, then some of them must be queued in the switch fabric 210. The switch fabric's ability to buffer or queue data packets is limited however. If too many internal data packets need to be queued and any of the limited switch fabric buffers become full, additional data packets that cannot be queued are deleted.
To avoid overflowing a given buffer in the switch fabric, the amount of data arriving at the associated contention point must not exceed the amount of data leaving the contention point by an amount greater than the buffer size when measured over all time intervals.
The rate of a data flow is defined as the amount of data sent divided by the time interval in which this data was sent. We use the term “steady rate” for a data flow that produces approximately the same rate when measured over any time interval, both short and long. A “bursty rate” is one where the rate of the data flow may vary significantly depending on whether the time interval is long or short. For a contention point with a specific buffer size, a buffer overflow can be avoided if each input port 202, 204, 206 sends packets to the contention point at a steady rate such that the sum of the packet input rates is equal to or less than the packet output rate from the contention point. This must be true for each of the system's contention points. If an input port 202, 204, 206 is assigned a rate at which it may send data packets to a contention point so as to avoid buffer overflow, it should send data packets at a steady pace that is at or below the given rate. If an input port 202, 204, 206 sends packets to a contention point in a bursty fashion, (i.e. it sends many packets to the point in a short period of time) then the instantaneous data packet rate is significantly greater than the average rate and switch fabric buffers might overflow. It is therefore important that an input port 202, 204, 206 send data packets to each of the contention points at steady rates by evenly spacing out packets sent to each contention point as much as possible. Deciding when any given input port should send a packet to any given contention point, a process known a scheduling, is vital to the performance of a switch.
An improved methodology for scheduling data packets to be sent into the switch fabric in a computationally efficient manner so as to reduce or eliminate the probability of buffer overflow at switch fabric contention points would be an improvement over the prior art.